package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * PathSum3
 * 437. 路径总和 III
 * https://leetcode.cn/problems/path-sum-iii/
 * <p>
 * Created on 2022/12/3
 *
 * @author lupeng
 */
public class PathSum4 {

    public static void main(String[] args) {
        TreeNode root = TreeMain.array2tree(new Integer[]{10, 5, -3, 3, 2, null, 11, 3, -2, null, 1});
        System.out.println(new PathSum4().pathSum(root, 8));
    }

    Map<Long, Integer> prefixSumCountMap = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        prefixSumCountMap.put(0L, 1);
        return dfs(root, targetSum, 0);
    }

    int dfs(TreeNode n, int targetSum, long pathSum) {
        if (n == null) {
            return 0;
        }
        pathSum += n.val;
        int ret = prefixSumCountMap.getOrDefault(pathSum - targetSum, 0);
        prefixSumCountMap.put(pathSum, prefixSumCountMap.getOrDefault(pathSum, 0) + 1);
        ret += dfs(n.left, targetSum, pathSum);
        ret += dfs(n.right, targetSum, pathSum);
        prefixSumCountMap.put(pathSum, prefixSumCountMap.get(pathSum) - 1);
        return ret;
    }
}
